/**
 * 
 */
package com.gwcloud.leetcode.hot100;

/**
 * @ClassName   : Leetcode0238 
 * @author      : ganwei 
 * @date        : 2020年5月22日
 * @Description : Leetcode0238 除自身以外数组的乘积
 */
public class Leetcode0238 {
    /**
     * -解题思路，空间复杂度O(N)
     */
	public int[] productExceptSelf(int[] nums) {
    	int[] l = new int[nums.length];
    	int[] r = new int[nums.length];
    	int[] answer = new int[nums.length];
    	
    	l[0] = 1;
    	for(int i = 1; i < nums.length; i++){
    		l[i] = nums[i-1] * l[i-1];
    	}
    	r[nums.length-1] = 1;
    	for(int i = nums.length-2; i >= 0; i--){
    		r[i] = nums[i+1] * r[i+1];
    	}
    	
    	for(int i = 0; i < nums.length; i++){
    		answer[i] = l[i] * r[i];
    	}
    	
    	return answer;
    }
	
    /**
     * -解题思路，空间复杂度O(1)
     */
	public int[] productExceptSelf_1(int[] nums){
		int n = nums.length;
		int[] answer = new int[n];
		
		answer[0] = 1;
		for(int i = 1; i < n; i++){
			answer[i] = nums[i-1] * answer[i-1];
		}
		int R = 1;
		for(int i = n-1; i >= 0; i--){
			answer[i] *= R;
			R *= nums[i];
		}
		
		return answer;
	}
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    }
}
